﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LinkedList
{
    public class Linkedlist<E>
    {
        private class Node
        {
            public E e;
            public Node next;
            public Node(E e, Node next)
            {
                this.e = e;
                this.next = next;
            }
            public Node(E e) : this(e, null) { }
            public Node() : this(default, null) { }
            public override string ToString()
            {
                return e.ToString();
            }
        }

        private Node head;
        private Node Dummyhead;//虚拟头结点
        private int size;
        public Linkedlist()
        {
            Dummyhead = new Node();
            head = null;
            size = 0;
        }

        //获取链表中元素个数
        public int getSize()
        {
            return size;
        }

        //判断链表是否为空
        public bool isEmpty()
        {
            return size == 0;
        }

        // 在链表的index(0-based)位置添加新的元素e
        // 在链表中不是一个常用的操作，练习用：）
        public void add(int index, E e)
        {

            if (index < 0 || index > size)
                throw new Exception("Add failed. Illegal index.");

            //if (index == 0)
            //    addFirst(e);
            //else
            //{
            //    Node prev = head;
            //    for (int i = 0; i < index - 1; i++)
            //        prev = prev.next;

            //    //            Node node = new Node(e);
            //    //            node.next = prev.next;
            //    //            prev.next = node;

            //    prev.next = new Node(e, prev.next);
            //    size++;
            //}


            Node prev = Dummyhead;
            for (int i = 0; i < index; i++)
                prev = prev.next;

            prev.next = new Node(e, prev.next);
            size++;
        }



        //向链表头部中添加元素
        public void addFirst(E e)
        {
            //Node node = new Node(e);
            //node.next = head;
            //head = node;

            //head = new Node(e, head);
            //size++;

            add(0, e);
        }

        // 在链表末尾添加新的元素e
        public void addLast(E e)
        {
            add(size, e);
        }





        // 获得链表的第index(0-based)个位置的元素
        // 在链表中不是一个常用的操作，练习用：）
        public E get(int index)
        {

            if (index < 0 || index >= size)
                throw new Exception("Get failed. Illegal index.");

            Node cur = Dummyhead.next;
            for (int i = 0; i < index; i++)
                cur = cur.next;
            return cur.e;
        }

        // 获得链表的第一个元素
        public E getFirst()
        {
            return get(0);
        }

        // 获得链表的最后一个元素
        public E getLast()
        {
            return get(size - 1);
        }

        // 修改链表的第index(0-based)个位置的元素为e
        // 在链表中不是一个常用的操作，练习用：）
        public void set(int index, E e)
        {
            if (index < 0 || index >= size)
                throw new Exception("Set failed. Illegal index.");

            Node cur = Dummyhead.next;
            for (int i = 0; i < index; i++)
                cur = cur.next;
            cur.e = e;
        }

        // 查找链表中是否有元素e
        public bool contains(E e)
        {
            Node cur = Dummyhead.next;
            while (cur != null)
            {
                if (cur.e.Equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }

        // 从链表中删除index(0-based)位置的元素, 返回删除的元素
        // 在链表中不是一个常用的操作，练习用：）
        public E remove(int index)
        {
            if (index < 0 || index >= size)
                throw new Exception("Remove failed. Index is illegal.");

            Node prev = Dummyhead;
            for (int i = 0; i < index; i++)
                prev = prev.next;

            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size--;

            return retNode.e;
        }

        // 从链表中删除第一个元素, 返回删除的元素
        public E removeFirst()
        {
            return remove(0);
        }

        // 从链表中删除最后一个元素, 返回删除的元素
        public E removeLast()
        {
            return remove(size - 1);
        }

        // 从链表中删除元素e
        public void removeElement(E e)
        {

            Node prev = Dummyhead;
            while (prev.next != null)
            {
                if (prev.next.e.Equals(e))
                    break;
                prev = prev.next;
            }

            if (prev.next != null)
            {
                Node delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
                size--;
            }
        }
        
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();

            //        Node cur = dummyHead.next;
            //        while(cur != null){
            //            res.append(cur + "->");
            //            cur = cur.next;
            //        }
            for (Node cur = Dummyhead.next; cur != null; cur = cur.next)
                res.Append(cur + "->");
            res.Append("NULL");
            return res.ToString();
        }

    }
}
